//外观数列
/*行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。*/
class Solution {
public:
    string countAndSay(int n) {
        string ret("1");
        if (n == 1)
            return ret;
        for (int i = 2; i <= n; i++) {
            string temp;
            int left = 0, right = 0;
            while (right <= ret.size()) {
                if (ret[left] == ret[right]) {
                    right++;
                } else if (right < ret.size() || ret[left] != ret[right]) {
                    temp += to_string(right - left);
                    temp += ret[left];
                    left = right;
                }
            }
            ret = temp;
        }
        return ret;
    }
};

//
/**/
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string c("croak");
        vector<int> hash(5);
        unordered_map<char, int> index;
        for (int i = 0; i < 5; i++)
            index[c[i]] = i;
        for (auto& c : croakOfFrogs) {
            if (index.count(c)) {
                if (c == 'c') {
                    if (hash[4])
                        hash[4]--;
                    hash[0]++;
                } else {
                    if (hash[index[c] - 1]) {
                        hash[index[c] - 1]--;
                        hash[index[c]]++;
                    } else {
                        return -1;
                    }
                }
            } else
                return -1;
        }
        for (int i = 0; i < 4; i++)
            if (hash[i])
                return -1;
        return hash[4];
    }
};